GATE PYQ

Link List

Q21.
The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution? struct node { int value; struct node next; }; Void rearrange(struct node list) { struct node p, q; int temp; if(!list|| !list-> next) return; p=list; q=list->next; while(q) { temp = p->value; p->value = q->value; q->value = temp; p = q->next; q = p?p->next:0; } }

Q22.
Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best-known algorithm to delete the node x from the list ?

Q23.
Suppose each set is represented as a linked list with elements in arbitray order. Which of the operations among union, intersection, membership, cardinality will be the slowest?

Q24.
Consider the function f defined below. struct item { int data; struct item * next; }; int f(struct item *p) { return ((p == NULL) || (p->next == NULL) || ((P->data <= p->next->data) && f(p->next))); } For a given linked list p, the function f returns 1 if and only if

Q25.
In the worst case, the number of comparisons needed to search a single linked list of length n for a given element is

Q26.
A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?

Q27.
The concatenation of two lists is to be performed on O(1) time. Which of the following implementations of a list should be used?

Q28.
For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons of

Q29.
Which of the following statements is true? I. As the number of entries in a hash table increases, the number of collisions increases. II. Recursive programs are efficient III. The worst case complexity for Quicksort is O(n^2) IV. Binary search using a linear linked list is efficient

Q30.
Linked lists are not suitable data structures for which one of the following problems?